#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left <= right)
        {
            // printf("left:%d,right:%d\n",left, right);
            int mid = (left + right) >> 1;
            if (nums[mid] == target)
                return mid;
            if (target <= nums[right])
                if (nums[mid] <= nums[right] && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            else if (target > nums[right])
                if (nums[right] < nums[left])
                    right = mid - 1;
                else
                    left = mid + 1, right = nums.size() - 1;
        }
        return -1;
    }
};